// 子串哈希，哈希表，Manacher
// https://soj.turingedu.cn/problem/60501/

class Sub_hash {
  private:
    // log_base (2 ^ 64) = 64 * ln 2 / ln base < 10.7, if base <= 62
    const int base = 29; // 请选择一个质数，否则哈希冲突致死
    ull po[maxn]; // po[i] == bsae ^ i
    int decoder[130];

  private:
    int len; // string length
    ull pre[maxn];

  public:
    Sub_hash() {
        po[0] = 1;
        for (int i = 1; i < maxn; ++i)
            po[i] = po[i - 1] * base;
        for (int i = 0; i < 26; ++i)
            decoder['a' + i] = i + 1;
    }
    void init(char *s) {
        if ((len = strlen(s)) == 0) return;

        pre[0] = decoder[s[0]];
        for (int i = 1; i < len; ++i)
            pre[i] = pre[i - 1] * base + decoder[s[i]];
    }

    ull ask(int l, int r) {
        if (l == 0) return pre[r];
        return pre[r] - pre[l - 1] * po[r - l + 1];
    }
} ash;

const int hash_size = 1e6 + 7;
int tot;
struct Node {
    ull val;
    Node *nex;
} pool[max_size], *head[hash_size];

inline int add(ull val) {
    int id = val % hash_size;
    for (auto p = head[id]; p > 0; p = p->nex)
        if (p->val == val) return 0;
    pool[++tot] = {val, head[id]};
    head[id] = pool + tot;
    return 1;
}

char str[maxn];
int d1[maxn]; // 以 i 为中心的回文串的奇半径
int d2[maxn]; // 以 i 为右中心的回文串的偶半径

int Manacher(char *s, int len) { // 返回本质不同的回文串数量
    int ans = 0;
    for (int i = 0, l = 0, r = -1; i < len; ++i) {
        int tmp = i > r ? 1 : min(d1[r - i + l], r - i + 1);
        ans += add(ash.ask(i, i)); // 枚举区间长为 1 
        while (i - tmp >= 0 && i + tmp < len && s[i - tmp] == s[i + tmp])
            ans += add(ash.ask(i - tmp, i + tmp)), ++tmp; // 在此处枚举区间，避免绝对重复的情况
        d1[i] = tmp--;
        if (i + tmp > r) l = i - tmp, r = i + tmp;
    }

    for (int i = 0, l = 0, r = -1; i < len; ++i) {
        int tmp = i > r ? 0 : min(d2[r - i + l + 1], r - i + 1);
        while (i - tmp - 1 >= 0 && i + tmp < len && s[i - tmp - 1] == s[i + tmp])
            ans += add(ash.ask(i - tmp - 1, i + tmp)), ++tmp;
        d2[i] = tmp--;
        if (i + tmp > r) l = i - tmp - 1, r = i + tmp;
    }
    return ans;
}
